62. 不同路径

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/unique-paths/

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
Alt text
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。

示例 1:

1
2
输入: m = 3, n = 2
输出: 3

解释:
从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

分析

对于想应用成动态规划，我们首先要考虑的就是将他转化成一个i步的问题，所以走到右下角的点实际上需要的是m+n-2步，这就变成了一个可量化的步骤，然后我们把它称之为第i步，这一题由于限定了只能向下和向右走，所以不存在绕圈的情况，所以第i步依赖于第i-1之和。

我们再从第一步开始，看看能不能推到第i步

首先有对角线是：m+n-2步，我们第一步开始推

1
2
3
4
5
6
7
8
9
10
11
step=1
0，1：1
1，0：1
step=2
0，2：1
1，1：2
2，0：1
step=3
0，3：1
1，2：1+2=3
2，1：(1,1)+(2,0)=3

可以看出来，很明显的当前位置依赖于上一步和他相邻的位置的和。现在还有个问题就是如何按照对角线的方式进行遍历。可以选择一个循环按照步数来进行遍历选择坐标。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * m for _ in range(n)]
        dp[0][0] = 1
        for step in range(1, m + n - 2 + 1):
            for y in range(step+1):
                x = step - y
                if x > n - 1 or y > m - 1:
                    continue
                nums = 0
                if 0 <= x - 1 <= n - 1:
                    nums += dp[x - 1][y]
                if 0 <= y - 1 <= m - 1:
                    nums += dp[x][y - 1]
                dp[x][y] = nums
        return dp[n - 1][m - 1]

Alt text

调优

可以看到很明显时间复杂度还是比较高的。我们想一想主要的耗时地方可能在于循环找y的部分做了比较多的无意义的工作，因为step可能是远大于m的，所以我们加上这一步，这样就可以删减掉很多无意义的循环:

1
max_y = min(step + 1, m)

既然在这一步以及做了判断了，那么

1
2
if x > n - 1 or y > m - 1:
    continue

关于y的校验的判断也可以去掉了。所以最终的代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:

    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * m for _ in range(n)]
        dp[0][0] = 1
        for step in range(1, m + n - 2 + 1):
            max_y = min(step + 1, m)
            for y in range(max_y):
                x = step - y
                if x > n - 1:
                    continue
                nums = 0
                if 0 <= x - 1 <= n - 1:
                    nums += dp[x - 1][y]
                if 0 <= y - 1 <= m - 1:
                    nums += dp[x][y - 1]
                dp[x][y] = nums
        return dp[n - 1][m - 1]

可以看到效果还是不错的。
Alt text